package com.cat.dataStructure02;

import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-of-interesting-subarrays/
 * @create 2025/10/22 19:11
 * @since JDK17
 */

public class Solution45 {
    public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) {
        long ans = 0;
        int n = nums.size(), sum = 0;
        int[] cnt = new int[Math.min(n + 1, modulo)];
        for (int x : nums) {
            sum += x % modulo == k ? 1 : 0; // 前缀和
            ans += cnt[(sum - k + modulo) % modulo];
            cnt[sum % modulo]++;
        }

        return ans;
    }
}
